1. Field of the Invention
This invention relates to the field of network systems, and in particular to the simulation of network architectures and configurations to evaluate performance.
2. Description of Related Art
Modeling is a proven technique for estimating the performance of systems. Such modeling is typically based on models of the components of the system and the interactions among components. In a typical performance model, the architecture of the system is encoded as a network of interconnected elements. Each element includes input and output nodes, and a corresponding functional model that describes the production of output node values, based on the input node values, and the state of the element. The network description specifies the interconnections among the input and output nodes of the elements comprising the system. The specification of the interconnections, or links, determines the correspondence between the output node values of each element to the input nodes of other elements.
An analytical evaluation of the performance of the modeled system is effected by specifying a set of initial conditions, if any, to each element, and a set of input values or parameters to the input nodes of the system. Various modeling techniques may be employed, depending upon the function of the system being modeled and the performance factors of interest. Information processing and communications systems are often modeled using stochastic models that describe the information transfer via a statistical generalization of the information being transferred and the performance and limitations of each element and link of the system. For example, an input to a processing element is described using statistics that describe an expected pattern of inputs, such as, for example, an average arrival rate of new messages, an average size of each message, and so on. Similarly, the capability of the processing element is described in terms of the average throughput rate, maximum queue length, and so on. The determination of the output characteristics of each processing element is typically based on classical xe2x80x9cQueuing Theoryxe2x80x9d models that can provide estimates of delay time, queue size, and other parameters associated with a sequential process. As is known in the art, queuing theory models provide a xe2x80x9csteady-statexe2x80x9d estimate of these output parameters. That is, statistically, if an average number of items having an average number of units arrives at a element that can process an average number of units per unit time, the output of the element will be an average number of items having an average processing delay relative to the input, the element itself will have an average queue length, and so on. Of particular significance, because the analytical model provides a xe2x80x9csteady-statexe2x80x9d estimate, the initial conditions of the system are not significant, because any out-of-the ordinary effects of initial conditions can be expected to diminish in time, as the system approaches the steady-state condition.
The analytical model processing system computes the results associated with each element, based on the element model, or transfer equation. Because one element""s computed output may affect another elements input, as determined by the interconnections within the modeled system, this computation is repeated until each of the elements provides a stable output. This process is similar to a conventional xe2x80x9cspread sheetxe2x80x9d program that computes the overall effect of a change to a value of a cell in the spread sheet by repeatedly processing the equations associated with the spread sheet until the effect of the changed value, if any, is reflected in every cell.
In the field of network simulations, analytical modeling techniques are particularly well suited for estimating such parameters as: a link utilization factor that identifies the volume of traffic flowing in each link, relative to the size, or bandwidth, of each link; a network latency factor associated with each pair of nodes in the network that identifies a composite of queuing delays, processing delays, and path delays between any two nodes in the network; and so on.
Analytical models, however, are not well suited for assessing the effects of protocol handling, including, for example, the effects of the segmentation of information items into packets, congestion control and packet discarding, retransmissions, weighted fairness algorithms, and so on. In like manner, the steady-state analytical models do not address the dynamics of traffic patterns nor, as mentioned above, the effects of initial or abnormal conditions. The steady-state analytical models primarily rely on traffic volume to determine the aforementioned link utilization and network latency performance measures. Also, the analytical modeling of the extremes of behavior is substantially more complex than merely modeling the average behavior, and the determination of such parameters as the peak delay time, or a profile of response times, in general, is rarely available using analytical models.
An alternative to analytical modeling is discrete-event simulation. In a discrete-event simulation, the network is also modeled using elements and links that interconnect elements, but the models utilized for each element are designed to provide a specific output response to a specific input event, rather than a statistical model. That is, for example, a model of a transmitter includes a model of a queue to receive a group of packets corresponding to an information item, and an output generator that removes each packet from the queue and places it at its output after a specified processing time, at the transmitter""s transmission rate. If additional packets arrive at the transmitter""s input, they are placed in the modeled queue, and wait their turn to be transmitted. Statistical parameters, such as the average number of packets in the transmitter""s queue, are determined by periodically monitoring the modeled queue to determine the actual number of packets that are in the queue at each monitored time. The packets that are placed at the output node of an element are propagated via the interconnection links, and arrive at the node at the other end of the link after a propagation delay associated with the link. Upon arrival, the packets are each similarly processed by the model associated with the receiving element.
Because discrete events are modeled, the models associated with each element or link can be explicit, and need not contain a closed-form analytical model. For example, the aforementioned transmitter may have alternative transmission paths for communicating each packet, based on a destination address contained within the packet. The transmitter model need merely contain a conditional statement that places each packet in the queue onto the appropriate output, based on the destination address of each packet. In like manner, the effects of transmission errors can be modeled by randomly introducing errors into each packet, depending upon parameters associated with the elements or links. A receiving device can be modeled to reject a packet if the number of randomly introduced errors exceed a given threshold, and the transmitter can be modeled to effect a retransmission of the packet upon notification of the rejection. In this manner, the actual packet throughput in the presence of random noise can be determined based on simulated packet transmissions in the presence of simulated noise. Depending upon the level of detail of the model, packet transformations can also be modeled, for example, by modeling a packet as it is processed by its associated protocol. For example, using the ISO-OSI protocol reference model, packets may be generated at an application layer and transformed through the various layers until the simulation models the transfer of bits at the physical layer. At each stage of the transformation, processing and queue delays may be introduced, error detection and processing may be modeled, and so on. Attempting to model such explicit behavior in a closed form analytical model is virtually impossible.
A discrete-event simulation of a network of reasonable size often involves the generation of hundreds of thousands of input events, and the subsequent processing and propagating of these events through the network until each modeled event arrives at its intended destination. Often, a realistic discrete-event simulation can run for hours or days on fairly powerful computers, and consume large amounts of memory resources as each generated and propagated event is tracked through the network. An analytical model of a similarly sized system, on the other hand, is typically run in a matter of seconds or minutes, and consumes a relatively small amount of data. That is, conventionally, the determination of detailed information regarding the performance of a network requires a substantial amount of time and resources, whereas the determination of overall performance measures can be determined quickly, provided that the appropriate theoretical models are available.
It is an object of this invention to provide a method of simulation that provides the ability to obtain detailed performance information at a substantially higher speed than conventional discrete-event simulation. It is a further object of this invention to provide a method of analytical modeling that provides more detailed performance measures than a conventional analytical model. It is a further object of this invention to provide a system that allows for the simulation of a network using the above methods.
These objects, and others, are achieved by providing a method of simulation that combines the advantages of both analytical modeling and discrete-event simulation. In a preferred embodiment of this invention, traffic on the network is modeled as a combination of xe2x80x9cbackground-trafficxe2x80x9d and xe2x80x9cexplicit-trafficxe2x80x9d. The background-traffic is primarily processed in an analytical form, except in the xe2x80x9ctime-vicinityxe2x80x9d of an explicit-traffic event. Explicit-traffic events are processed using discrete-event simulation, but the modeled effects are dependent upon the background-traffic and corresponding particularized background-traffic events.
Immediately before and during each discrete-event time, the background-traffic is processed to produce discrete background-traffic events. These background-traffic events are processed by each element and link model as discrete events that are simulated along with the actual explicit-events. At all other times, the background-traffic is processed using conventional analytical modeling techniques. In a preferred embodiment of this invention, the background-traffic model includes timing parameters, and the simulation method also provides for a time-varying analytical modeling technique.